package model;

@SuppressWarnings("unchecked")
public class MergeSort extends Sorter {

	public MergeSort() {
	super();
	statistics = new Statistics();
    }

    private void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
	int i = lo, j = mid;
	for (int k = lo; k < hi; k++) {
	    //check
	    statistics.incrementChecks();
	    
	    if (i == mid){
			aux[k] = a[j++];
		    }
		    else if (j == hi){
			aux[k] = a[i++];
		    }
		    else if (a[j].compareTo(a[i]) < 0){
			aux[k] = a[j++];
		    }
		    else{
			aux[k] = a[i++];
		    }
		
	}

	// copy back
	for (int k = lo; k < hi; k++)
		a[k] = aux[k];
	
		// add to queue:
		if (simulation) {
			Integer[] tmp = new Integer[a.length];
			for (int j2 = 0; j2 < a.length; j2++) {
				tmp[j2] = (Integer) a[j2];
			}
			PushMergeListToQueue(tmp);
		}
    }

    private void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
	// base case
	if (hi - lo <= 1)
	    return;

	// sort each half, recursively
	int mid = lo + (hi - lo) / 2;
	sort(a, aux, lo, mid);
	sort(a, aux, mid, hi);

	// merge back together
	merge(a, aux, lo, mid, hi);
    }

    @Override
    public void sort(Comparable[] workArray) {
	int N = workArray.length;
	long beforeTime = System.nanoTime();
	
	Comparable[] aux = new Comparable[N];
	sort(workArray, aux, 0, N);
	
	long afterTime = System.nanoTime();
	statistics.setRunTime(afterTime - beforeTime);
    }

    @Override
    public int getComplexity(int arraySize) {
	return (int) (Math.pow(arraySize, 2) * .5);
    }

}
